class Solution {
    typedef pair<string,int> PSI;
    struct cmp
    {
        bool operator()(const PSI& a,const PSI& b)
        {
            if(a.second==b.second)
            {
                return a.first<b.first;
            }
            return a.second>b.second;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> hash;
        for(auto& s:words)hash[s]++;
        priority_queue<PSI,vector<PSI>,cmp>heap;
        for(auto& psi:hash)
        {
            heap.push(psi);
            if(heap.size()>k)heap.pop();
        }
        vector<string> ret(k);
        for(int i=k-1;i>=0;i--)
        {
            ret[i]=heap.top().first;
            heap.pop();
        }
        return ret;
    }
};
